package 每日一题;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 2594. 修车的最少时间
 * 提示
 * 中等
 * 78
 * 相关企业
 * 给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
 *
 * 同时给你一个整数 cars ，表示总共需要修理的汽车数目。
 *
 * 请你返回修理所有汽车 最少 需要多少时间。
 *
 * 注意：所有机械工可以同时修理汽车。
 *
 *
 *
 * 示例 1：
 *
 * 输入：ranks = [4,2,3,1], cars = 10
 * 输出：16
 * 解释：
 * - 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
 * - 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
 * - 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
 * - 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
 * 16 分钟是修理完所有车需要的最少时间。
 * 示例 2：
 *
 * 输入：ranks = [5,1,8], cars = 6
 * 输出：16
 * 解释：
 * - 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
 * - 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
 * - 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。
 * 16 分钟时修理完所有车需要的最少时间。
 *
 *
 * 提示：
 *
 * 1 <= ranks.length <= 105
 * 1 <= ranks[i] <= 100
 * 1 <= cars <= 106
 */
public class T2594_修车的最少时间 {

    //贪心思想 按能力值排序 尽量让修的快的 多修车
    // 新来一辆车让谁修？  让增加一辆车 修车时间总时间最小的人修
    public long repairCars(int[] ranks, int cars) {
        //int[]{能力值,修车数量,再增加一辆车总时间}
        Queue<long[]> queue = new PriorityQueue<>(new Comparator<long[]>() {
            @Override
            public int compare(long[] o1, long[] o2) {
                return (int) (o1[2] - o2[2]);
            }
        });

        for (int rank : ranks) {
            long[] mechanics = new long[]{rank, 0, rank};
            queue.offer(mechanics);
        }
        long max = 0;
        //每增加一辆车 从队列中找出 增加一辆车后总时间最少的人
        for (int i = 1; i <= cars; i++) {
            long[] mechanics = queue.poll();
            max = Math.max(max, mechanics[2]);
            mechanics[1] = mechanics[1] + 1;
            mechanics[2] = mechanics[0] * (mechanics[1] + 1) * (mechanics[1] + 1);
            queue.offer(mechanics);
        }

        return max;
    }

    public static void main(String[] args) {
        T2594_修车的最少时间 test = new T2594_修车的最少时间();
        long l = test.repairCars(new int[]{4, 2, 3, 1}, 10);

    }

}
